package com.hy.dp.bagProblem.fullBag;

public class ClimbStairs {


    /**
     * 70. 爬楼梯
     * 力扣题目链接
     *
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     *
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     *
     * 注意：给定 n 是一个正整数。
     * 示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
     *
     * 1 阶 + 1 阶 + 1 阶
     * 1 阶 + 2 阶
     * 2 阶 + 1 阶
     * 思路
     * 这道题目 我们在动态规划：爬楼梯 中已经讲过一次了，原题其实是一道简单动规的题目。
     *
     * 改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
     * 1阶，2阶，.... m阶就是物品，楼顶就是背包。
     * 每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
     * 问跳到楼顶有几种方法其实就是问装满背包有几种方法。
     * 此时大家应该发现这就是一个完全背包问题了！
     * 动规五部曲分析如下：
     *
     * 1.确定dp数组以及下标的含义
     * dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法。
     *
     * 2.确定递推公式
     * 在动态规划：494.目标和 、 动态规划：518.零钱兑换II、动态规划：377. 组合总和 Ⅳ中我们都讲过了，求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
     *
     * 本题呢，dp[i]有几种来源，dp[i - 1]，dp[i - 2]，dp[i - 3] 等等，即：dp[i - j]
     *
     * 那么递推公式为：dp[i] += dp[i - j]
     *
     * 3.dp数组如何初始化
     * 既然递归公式是 dp[i] += dp[i - j]，那么dp[0] 一定为1，dp[0]是递归中一切数值的基础所在，如果dp[0]是0的话，其他数值都是0了。
     *
     * 下标非0的dp[i]初始化为0，因为dp[i]是靠dp[i-j]累计上来的，dp[i]本身为0这样才不会影响结果
     *
     * 4.确定遍历顺序
     * 这是背包里求排列问题，即：1、2 步 和 2、1 步都是上三个台阶，但是这两种方法不一样！
     *
     * 所以需将target放在外循环，将nums放在内循环。
     *
     * 每一步可以走多次，这是完全背包，内循环需要从前向后遍历。
     *
     * 5.举例来推导dp数组
     * dp[0] = 1
     * dp[1] = 1
     * dp[2] = 2
     * dp[3] = 3
     * dp[4] = 5
     * dp[5] = 8
     * @return
     */
    public static int climbStairs(int [] nums,int n){
        // 1. 定义dp数组以及下标定义
        int [] dp = new int[n + 1];
        // 2. 推导 递推式

        // 3.初始化
        dp[0] = 1;
        // 4.循环遍历   先循环  背包    再循环 物品
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]){
                    dp[i] += dp[i -nums[j]];
                }
            }
        }
        // 5.结果
        return dp[n];
    }
    public static void main(String[] args) {
        int [] nums = {1,2};
        int n = 5;
        System.out.println("res: "+climbStairs(nums,n));
    }
}
